package pers.qianyu.month_202011.date_20201113;

import java.util.*;

/**
 * 752. 打开转盘锁
 * https://leetcode-cn.com/problems/open-the-lock/
 *
 * @author mizzle rain
 * @date 2020-11-13 17:04
 */
public class OpenLock {
    public int openLock(String[] deadends, String target) {
        Queue<String> q = new LinkedList<>();
        HashSet<String> visited = new HashSet<>();
        q.add("0000");
        visited.add("0000");
        int step = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                String cur = q.poll();
                if (!isValid(deadends, cur)) {
                    continue;
                }
                if (cur.equals(target)) {
                    return step;
                }
                visited.add(cur);

                for (int k = 0; k < 4; k++) {
                    String next = next(k, cur);
                    if (!visited.contains(next)) {
                        q.add(next);
                        visited.add(next);
                    }
                    String pre = pre(k, cur);
                    if (!visited.contains(pre)) {
                        q.add(pre);
                        visited.add(pre);
                    }
                }
            }
            step++;
        }
        return -1;
    }

    private boolean isValid(String[] deadends, String result) {
        return Arrays.stream(deadends).noneMatch(result::equals);
    }

    private String next(int index, String target) {
        char[] arr = target.toCharArray();
        if (arr[index] == '9') {
            arr[index] = '0';
        } else {
            arr[index] = (char) (arr[index] + 1);
        }
        return new String(arr);
    }

    private String pre(int index, String target) {
        char[] arr = target.toCharArray();
        if (arr[index] == '0') {
            arr[index] = '9';
        } else {
            arr[index] = (char) (arr[index] - 1);
        }
        return new String(arr);
    }

    public static void main(String[] args) {
        String[] deadends = {"8887", "8889", "8878", "8898", "8788", "8988", "7888", "9888"};
        String target = "8888";
        int result = new OpenLock().openLock(deadends, target);
        System.out.println("result = " + result);
    }
}
